//#include<bits/stdc++.h>
//using namespace std;
//void ff() {
//
//}
//int main() {
//	int n;
//	cin >> n;
//	while (n--) {
//		int a;
//		cin >> a;
//		string s;
//		cin >> s;
//		int flag = 0;
//		int l = 0, r = s.size() - 1;
//		while (l <= r) {
//			while (s[l] == '0' && l <= r)l++;
//			if(l<=r)
//			flag++;
//			while (s[l] == '1'&&l<=r)l++;
//			if(l<=r)
//			flag++;
//		}
//		cout << flag << endl;
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//void ff() {
//
//}
//int arr[200010];
//int brr[200010];
//int main() {
//	int n;
//	cin >> n;
//	while (n--) {
//		int Max = 0;
//		int  L = 0, R = 0;
//		int a;
//		cin >> a;
//		memset(brr, 0, sizeof brr);
//		for (int i = 1; i <= a; i++)cin >> arr[i];
//		if (a == 1)
//			cout << 1<<' '<<1 << endl;
//		else{
//			int l = 1, r = 1;
//			for (; r <= a; r++) {
//				brr[arr[r]]++;
//				if (brr[arr[r]] > 1) {
//					for (int i = l; i <= r; i++)brr[arr[i]]--;
//					int i = l;
//					while(arr[i]!=arr[r])i++;
//					if (i - l > r - i - 1)
//					{
//						if (Max < i - l)
//						{
//							Max = i - l;
//						L = l;
//						R=i-1;
//						}
//					}
//					else
//					{
//						if (Max < r-i-1)
//						{
//							Max = r-i-1;
//							 L = i+1;
//							 R=r-1;
//						}
//					}
//					l = r, r--;
//				}
//			}
//			if (Max == 0)
//				cout  << 0 << endl;
//			else
//				cout << L << ' ' << R << endl;
//		}
//
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//void ff() {
//
//}
//int arr[200010];
//int brr[200010];
//int main() {
//	int n;
//	cin >> n;
//	while (n--) {
//		int Max = 0;
//		int  L = 0, R = 0;
//		int a;
//		cin >> a;
//		memset(brr, 0, sizeof brr);
//		for (int i = 1; i <= a; i++)cin >> arr[i];
//		for (int i = 1; i <= a; i++)brr[arr[i]]++;
//		int l = 1, r = 1;
//		if (a == 1)
//		{
//			cout << "1 1" << endl;
//			continue;
//		}
//		for (r; r <= a; r++) {
//			if (brr[arr[r]] == 1);
//			else if (brr[arr[r]] > 1) {
//				if (Max < r - l) {
//					Max = r - l;
//					R = r - 1, L = l;
//				}
//				l = r + 1;
//			}
//			else;
//		}
//		if (Max < r - l) {
//			Max = r - l;
//			R = r - 1, L = l;
//		}
//		if (Max == 0)cout << 0 << endl;
//		else
//			cout << L << ' ' << R << endl;
//		if (a == 1)
//			cout << 1 << ' ' << 1 << endl;
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//long long sum[200010];
//long long arr[200010];
//int main() {
//	int n;
//	cin >> n;
//	while (n--) {
//		int a = 0;
//		cin >> a;
//		for (int i = 1; i <= a; i++)cin >> arr[i];
//		for (int i = 1; i <= a; i++)
//			sum[i] += sum[i - 1] + abs(arr[i]);
//		int l = 1, r = a;
//		long long ans = 0;
//		while (l <= r) {
//			if (arr[l] >= 0)
//				ans += arr[l++];
//			else if (l <= r && arr[r] < 0)ans += abs(arr[r--]);
//			else if (l <= r) {
//				int L = l, R = r;
//				while (L <= R && arr[L] < 0)L++;
//				L--;
//				while (L <= R && arr[R] >= 0)R--;
//				R++;
//				if (sum[L] - sum[l - 1] > sum[r] - sum[R - 1])
//					r = L;
//				else
//					l = R;
//			}
//			else;
//		}
//		cout << ans << endl;
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//long long sum[200010];
//long long arr[200010];
//int main() {
//	int n;
//	cin >> n;
//	while (n--) {
//		int a = 0;
//		cin >> a;
//		for (int i = 1; i <= a; i++)cin >> arr[i];
//		for (int i = 1; i <= a; i++)
//			sum[i] += sum[i - 1] + abs(arr[i]);
//		int l = 1, r = a;
//		long long ans = 0;
//		int l = 1;
//		for(int i=1;i<=a;i++)
//				if (sum[i-1] - sum[l - 1] > sum[r] - sum[R - 1])
//					r = L;
//				else
//					l = R;
//			}
//			else;
//		}
//		cout << ans << endl;
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct date {
//	int a, b;
//	bool operator> (const date d)const {
//		return a < d.a;
//	}
//};
//int main() {
//	date d1, d2, d3;
//	d1.a = 10, d1.b = 3;
//	d2.a = 11, d2.b = 2;
//	d3.a = 13, d3.b = 1;
//	priority_queue<date>p;
//	p.push(d1);
//	p.push(d2);
//	p.push(d3);
//	while (!p.empty())
//	{
//		cout << p.top().a << endl;;
//		p.pop();
//	}
//}
//long long sum[200010];
//long long arr[200010];
//int main() {
//	int n;
//	cin >> n;
//	while (n--) {
//		int a = 0;
//		cin >> a;
//		for (int i = 1; i <= a; i++)cin >> arr[i];
//		for (int i = 1; i <= a; i++)
//			sum[i] += sum[i - 1] + abs(arr[i]);
//		int l = 1, r = a;
//		long long ans = 0;
//		while (l <= r) {
//			if (arr[l] >= 0)
//				ans += arr[l++];
//			else if (l <= r && arr[r] < 0)ans += abs(arr[r--]);
//			else if (l <= r) {
//				long long Max = 0x3f3f3f3f3f3f3f3f;
//				int flag = 0;
//				int pos = 1;
//				for (int i = l; i <= r; i++) {
//					if (arr[i] < 0) {
//						if (Max > sum[r] - sum[i]) {
//							flag = -1;
//							Max = sum[r] - sum[i];
//							pos = i;
//						}
//					}
//					else {
//						if (Max > sum[i-1] - sum[l-1]) {
//							flag = 1;
//							Max = sum[i-1] - sum[l-1];
//							pos = i;
//						}
//					}
//				}
//				if (flag == -1) {
//					r = pos;
//				}
//				else
//					l = pos;
//			}
//			else;
//		}
//		cout << ans << endl;
//	}
//	return 0;
//}

//#include <iostream>
//using namespace std;
//int arr[100010];
//int main()
//{
//    int n, m, x;
//    cin >> n >> m >> x;
//    for (int i = 1; i <= n; i++)
//        cin >> arr[i];
//    while (m--) {
//        int a, b;
//        cin >> a >> b;
//        int flag = 0;
//        for (int i = a; i <= b && flag == 0; i++) {
//            for (int j = a + 1; j <= b && flag == 0; j++)
//                if ((arr[i] ^ arr[j]) == x)
//                {
//                    cout << "yes" << endl;
//                    flag = 1;
//                }
//        }
//        if (flag == 0)
//            cout << "no" << endl;
//    }
//    return 0;
//}
//#include <iostream>
//using namespace std;
//typedef long long LL;
//typedef long long ll;
//long long mod = 998244353;
//LL kmi(LL a, LL b) {
//    LL ans = 1;
//    while (b) {
//        if (b & 1)
//            ans =ans* a%mod;
//        b >>= 1;
//        a =a* a% mod;
//    }
//    return ans;
//}
//ll ksm(ll a, ll b) {
//    ll res = 1;
//    while (b) {
//        if (b & 1)                    // �����ǰb�Ķ���������Ϊ1��������
//            res = res * a % mod;       // ������ϵ�ǰa
//        a = a * a % mod;               // ��һλ��a��ֵ����ƽ����
//        b >>= 1;                     // b����һλ��������
//    }
//    return res;
//}
//int main()
//{
//    LL m;
//    cin >> m;
//    LL a = 1, b = 1;
//    while (m--) {
//        LL x, y;
//        cin >> x >> y;
//        a *= x;
//        b *= y;
//        a %= mod;
//        b %= mod;
//    }
//    cout << a * ksm(b, mod - 2)%mod;
//    return 0;
//}
//#include <bits/stdc++.h>
//using namespace std;
//using ll = long long;
//const ll mod = 998244353;
//const int N = 1e5 + 9;
//ll n, x[N], y[N];
//
//ll qsm(ll q, ll m) {
//    ll ans = 1;
//    while (m) {
//        if (m & 1)ans = ans * q % mod;
//        q = q * q % mod; m >>= 1;
//    }
//    return ans;
//}
//
//ll inv(ll q) { return qsm(q, mod - 2); }
//
//void solve() {
//    cin >> n;
//    for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];
//    ll a = x[n] * inv(y[n]) % mod, b = 1;
//    for (int i = n - 1; i > 0; i--) {
//        ll p = x[i] * inv(y[i]) % mod, q = (y[i] - x[i]) * inv(y[i]) % mod;
//        a = (p + q * a % mod) % mod, b = (q * b % mod + 1) % mod;
//        //a=x[i]*inv(y[i])+(y[i]-x[i])*inv(y[i])*a;
//        //b=(y[i]-x[i])*inv(y[i])*b+1;
//    }
//    cout << ((-b * inv(a - 1)) % mod + mod) % mod;
//}
//
//int main() {
//    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//    int t = 1;
//    //cin>>t;
//    while (t--) {
//        solve();
//    }
//    return 0;
//}
//#include<iostream>
//#include<string>
//#include<sstream>
//int main() {
//	std::stringstream  ss;
//	std::string s = "111";
//	ss << s;
//	std::string s1;
//	ss >> s1;
//	std::cout << s1;
//}
//#include<iostream>
//using namespace std;
//int a[1010][1010], b[1010][1010], c[1010][1010];
//int main() {
//	int n,q;
//	cin >> n >> q;
//	long long sum = 0;
//	while (q--)
//	{
//		int x, y, z;
//		cin >> x >> y >> z;
//		a[x][y]+=1;
//		b[x][z]++;
//		c[y][z]++;
//		if (a[x][y] == n)
//			sum++;
//		if (b[x][z] == n)
//			sum++;
//		if (c[y][z] == n)
//			sum++;
//		cout << sum << endl;
//	}
//}
//#include<iostream>
//using namespace std;
//int main() {
//	for (int i = 1; i < 32; i++) {
//		for(int j=i;j<32;j++)
//			for(int k=j;k<32;k++)
//				if (i!=6&&i * i + j * j + k * k == 1000)
//				{
//					cout << i;
//					return 0;
//				}
//	}
//
//}
//#include<iostream>
//using namespace std;
//int arr[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//int main() {
//	int y = 20141109;
//	int sum = 0;
//	while (true)
//	{
//		y++;
//		int year = y / 10000;
//		int mon = y % 10000 / 100;
//		int day = y % 100;
//		if (mon > 0 && mon < 13) {
//			int flag = 0;
//			if ((year % 4 == 0 && y % 100 != 0) || y % 400 == 0)
//				if (mon == 2)flag = 1;
//			if (day > 0 && day <= arr[mon] + flag)
//				sum++;
//			if (sum == 1000)
//			{
//				printf("%d-%02d-%02d", year, mon, day);
//				return 0;
//			}
//		}
//	}
//
//}
//#include<iostream>
//#include<string>
//#include<bits/stdc++.h>
//using namespace std;
//int main() {
//	for (int i = 2; i < 10000; i++) {
//		int a = i * i;
//		int b = i * i * i;
//		string s = to_string(a) + to_string(b);
//		sort(s.begin(), s.end());
//		if (s.size() != 10)continue;
//		int flag = 0;
//		for (int i = 0; i < 10; i++)
//			if (i != s[i] - '0')
//				flag = 1;
//		if (flag == 0)
//		{
//			cout << i;
//			return 0;
//			}
//	}
//}
//#include <iostream>
//using namespace std;
//int f(int n) {
//    int drink = n;
//    int gaizi = 0;
//    int sum = 0;
//    while (drink) {
//        sum += drink;
//        gaizi += drink;
//        drink = 0;
//        
//        drink = gaizi / 3;
//        gaizi %= 3;
//    }
//    return sum;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    cout << f(n);
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main() {
//	int sum = 0;
//	for (int i = 10; i < 100; i++) {
//		int a = i;
//		int b = i % 10 * 10 + i / 10;
//		if (a - b == 27)
//		{		cout << i << endl;
//		sum++;
//	}
//	}
//	cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main() {
//	int i = 1;
//	while (i < 236) {
//		int j = i;
//		int sum = 236;
//		while (sum > 0)
//		{
//			sum -= j;
//			j++;
//		}
//		if (sum == 0) {
//			cout << i;
//			return 0;
//		}
//		i++;
//	}
//}
//#include<bits/stdc++.h>
//using namespace std;
//bool is[10];
//int arr[4][4];
//int xrr[8] = {1,1,1,0,0,-1,-1,-1};
//int yrr[8] = { 1,0,-1,1,-1,1,0,-1 };
//bool is(int x, int y) {
//	for (int i = 0; i < 8; i++) {
//		int _x = x + xrr[i];
//		int _y = y + yrr[i];
//		if (_x < 0 || _x>3 || _y < 0 || _y>0)continue;
//		if (abs(arr[x][y] - arr[_x][_y] == 1))
//			return 0;
//	}
//	return 1;
//}
//int main() {
//	arr[0][0] = arr[3][3] = -10;
//
//	for (int i1 = 0; i1 < 10; i1++)
//	{
//		arr[]
//		for (int i2 = 0; i2 < 10; i2++)
//			for (int i3 = 0; i3 < 10; i3++)
//				for (int i4 = 0; i4 < 10; i4++)
//					for (int i5 = 0; i5 < 10; i5++)
//						for (int i6 = 0; i6 < 10; i6++)
//							for (int i7 = 0; i7 < 10; i7++)
//								for (int i8 = 0; i8 < 10; i8++)
//									for (int i9 = 0; i9 < 10; i9++)
//										for (int i10 = 0; i10 < 10; i10++)
//	}
//}
//#include <iostream>
//using namespace std;
//int vis[10];
//int a[5][5];
//int sum = 0;
//int dx[8] = { -1, -1,-1,0, 0,1,1,1 };
//int dy[8] = { 0, -1,1,1, -1,1,0,-1 };
//int lim(int t, int x, int y) {
//    for (int i = 0; i < 8; i++) {
//        int nx = x + dx[i];
//        int ny = y + dy[i];
//        if (a[nx][ny] == -3) continue;
//        if (a[nx][ny] - t == 1 || a[nx][ny] - t == -1) return 0;
//    }
//    return 1;
//}
//
//void dfs(int x, int y) {
//    if (x == 3 && y > 3) {
//        sum++;
//        return;
//    }
//    if (y > 4) {
//        x++;
//        y = 1;
//    }
//    for (int i = 0; i <= 9; i++) {
//        if (vis[i] || !lim(i, x, y)) continue;
//        vis[i] = 1;
//        a[x][y] = i;
//        dfs(x, y + 1);
//        vis[i] = 0;
//        a[x][y] = -3;
//    }
//    return;
//}
//
//
//
//int main() {
//    for (int i = 0; i <= 5; i++) {
//        for (int j = 0; j <= 5; j++) {
//            a[i][j] = -3;
//        }
//    }
//    dfs(1, 2);
//    cout << sum;
//    return 0;
//}
//#include<iostream>
//using namespace std;
//int arr[12];
//bool is[14];
//int dfs(int pos) {
//	if (pos == 12)
//	{
//		/*for (int i = 0; i < 12; i++)
//		{
//			cout << arr[i] << ' ';
//
//		}
//		cout << endl;*/
//		return 1;
//	}
//	int sum = 0;
//	for (int i = 1; i < 14; i++)
//	{
//		if (is[i])continue;
//		arr[pos] = i;
//		is[i] = 1;
//		if (pos == 2)
//			if (arr[0] + arr[1] != arr[2])
//			{
//				is[i] = 0;
//				continue;
//			}
//		if(pos==5)
//			if (arr[pos-2] - arr[pos-1] != arr[pos])
//			{
//				is[i] = 0;
//				continue;
//			}
//		if (pos == 8)
//			if (arr[pos - 2] * arr[pos - 1] != arr[pos])
//			{
//				is[i] = 0;
//				continue;
//			}
//		if (pos == 11)
//			if (arr[pos - 2] / arr[pos - 1] != arr[pos] || arr[pos - 2] % arr[pos - 1] != 0)
//			{
//				is[i] = 0;
//				continue;
//			}
//		sum+=dfs(pos + 1);
//		is[i] = 0;
//	}
//	return sum;
//}
//int main() {
//	cout << dfs(0);
//}
//#include <iostream>
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 0; i * i * 4 <= n; i++) {
//        for (int j = i; i * i + j * j * 3 <= n; j++)
//            for (int k = j; i * i + j * j + k * k * 2 <= n; k++) {
//                {
//                    int L = n - i * i - j * j - k * k;
//                    int l = sqrt(L);
//                    if (l * l == L)
//                    {
//                        cout << i << ' ' << j << ' ' << k << ' ' << l;
//                        return 0;
//                    }
//                }
//            }
//    }
//    return 0;
//}
#include<bits/stdc++.h>
using namespace std;
//bool IS[10];
//int arr[3][4];
//int xrr[8] = {1,1,1,0,0,-1,-1,-1};
//int yrr[8] = { 1,0,-1,1,-1,1,0,-1 };
//bool is(int x, int y) {
//	for (int i = 0; i < 8; i++) {
//		int _x = x + xrr[i];
//		int _y = y + yrr[i];
//		if (_x < 0 || _x>2 || _y < 0 || _y>3)continue;
//		if (abs(arr[x][y] - arr[_x][_y]) == 1)
//			return 0;
//	}
//	return 1;
//}
//vector<pair<int, int>>v(10); 
//int dfs(int pos) {
//	if (pos == 10)
//		return 1;
//	int sum = 0;
//	for (int i = 0; i < 10; i++) {
//		if (IS[i])continue;
//		IS[i] = true;
//		arr[v[pos].first][v[pos].second] = i;
//		if (is(v[pos].first, v[pos].second) == 0)
//		{
//			IS[i] = 0;
//			continue;
//		}
//		sum += dfs(pos + 1);
//		IS[i] = 0;
//	}
//	arr[v[pos].first][v[pos].second] = -10;
//	return sum;
//}
//int main() {
//	for (int i = 0; i < 3; i++)for (int j = 0; j < 4; j++)arr[i][j] = -10;
//	arr[0][0] = -10, arr[2][3] = -10;
//	v[0] = { 0,1 };
//	v[1] = { 0,2 };
//	v[2] = { 0,3 };
//	v[3] = { 1,0 };
//	v[4] = { 1,1 };
//	v[5] = { 1,2 };
//	v[6] = { 1,3 };
//	v[7] = { 2,0 };
//	v[8] = { 2,1 };
//	v[9] = { 2,2 };
//	cout << dfs(0);
//}
//int main() {
//	double a=2.5007134, b=0.0051;
//	double arr[6] = { 0,0.4,0.8,1.2,1.6,2.0 };
//	double brr[6] = { 0.0003,1.0054,2.0085,3.0094,4.0071,5.0012 };
//	double crr[6] = { 0.0003,1.0068,2.0102,3.0107,4.0081,5.0014 };
//	double Max = 0;
//	for (int i = 0; i < 6; i++)
//	{
//		double sum = a * arr[i] + b;
//		Max = max(Max, fabs(sum - brr[i]));
//		Max = max(Max, fabs(sum - crr[i]));
//	}
//	printf("%lf", Max);
//}
//#include<bits/stdc++.h>
//
//
//class Solution {
//    map<char, int>mp;
//public:
//    int check()
//    {
//        if (mp['a'] && mp['e'] && mp['i'] && mp['o'] && mp['u'])
//            return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
//        return 0;
//    }
//    int countOfSubstrings(string word, int k) {
//        mp.clear();
//        int sum = 0;
//        int flag = 0;
//        int l = 0, r = 0;
//        for (; r < word.size(); r++)
//        {
//
//            mp[word[r]]++;
//            int num = check();
//            if (num)
//            {
//                if (num + k == r - l + 1)
//                {
//                    sum++;
//                }
//                else if (num + k < r - l + 1)
//                {
//                    int cha = (r - l + 1) - num - k;
//                    for (l;l<r&& cha; l++)
//                    {
//                        mp[word[l]]--;
//                        cha--;
//                    }
//                    mp[word[r]]--;
//                    r--;
//                }
//            }
//        }
//        r--;
//        while (l < r)
//        {
//            mp[word[l]]--;
//            l++;
//            int num = check();
//            if (num == 0)
//                break;
//            if (r - l + 1 == num + k)
//                sum++;
//        }
//        return sum;
//    }
//};
//int main()
//{
//    cout<<Solution().countOfSubstrings("aiouea",0);
//}

//#include<bits/stdc++.h>
//using namespace std;
//stack<char>fuhao;
//stack<long>shuzi;
//map<char, long long>mp;
//void value()
//{
//    char ch = fuhao.top();
//    fuhao.pop();
//    long long num1 = shuzi.top();
//    shuzi.pop();
//    long long num2 = shuzi.top();
//    shuzi.pop();
//    if (ch == '+')
//        num2 += num1;
//    else if (ch == '-')
//        num2 -= num1;
//    else if (ch == '*')
//        num2 *= num1;
//    else if (ch == '/')
//        num2 /= num1;
//    shuzi.push(num2);
//}
//int main()
//{
//    mp.insert({ '+',1 });
//    mp.insert({ '-',1 });
//    mp.insert({ '*',2 });
//    mp.insert({ '/',2 });
//    string s;
//    cin >> s;
//    long long sum = 0;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] >= '0' && s[i] <= '9')
//        {
//            string s1;
//            while (i<s.size()&&s[i] >= '0' && s[i] <= '9')
//                s1 += s[i++];
//            i--;
//            long long num = stol(s1);
//            shuzi.push(num);
//        }
//        else
//        {
//            if (s[i] == '(')
//                fuhao.push(s[i]);
//            else if (s[i] == ')')
//            {
//                while(fuhao.top()!='(')
//                value();
//                fuhao.pop();//ɾ��������
//            }
//            else 
//            {
//                if (fuhao.size()&&mp[s[i]]<=mp[fuhao.top()])
//                {
//                    
//                    value();
//                }
//                fuhao.push(s[i]);
//            }
//
//        }
//    }
//    while(shuzi.size()>1)
//    value();
//    cout << shuzi.top();
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct t{
//	int a;
//	bool operator<(struct t t1)const
//	{
//		return a < t1.a;
//	}
//};
//int main()
//{
//	priority_queue<t>q;
//	t t1{ 0 };
//	t t2{ 1 };
//	q.push(t1);
//	q.push(t2);
//	t t3= q.top();
//	vector<int>v{1,2,3,4,5,6};
//	sort(v.begin(), v.end(), greater<int>());
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//vector<int>v;
//int n;
//bool xie1[20], xie2[20], lie[10];
//void dfs(int pos)//�ӵ�i�п�ʼ
//{
//    if (pos == n + 1)
//    {
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                if (v[i-1]!=j)cout << ".";
//                else
//                    cout << 'Q';
//            }
//            cout << endl;
//        }
//        cout << endl;
//        return;
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        if (lie[i] || xie1[i + pos] || xie2[i - pos + n])
//            continue;
//        lie[i] = xie1[i + pos] = xie2[i - pos + n] = 1;
//        v.push_back(i);
//        dfs(pos + 1);
//        lie[i] = xie1[i + pos] = xie2[i - pos + n] = 0;
//        v.pop_back();
//    }
//}
//int main()
//{
//    cin >> n;
//    dfs(1);
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[110][110];
//int n, m;
//typedef pair<int, int> PII;
//PII brr[4] = { {0,1},{1,0},{-1,0},{0,-1} };
//bool is[110][110];
//queue<PII>q;
//int bfs()
//{
//    q.push({ 1,1 });
//    is[1][1] = 1;
//    int sum = 0;
//    while (q.empty() == 0)
//    {
//        int num = q.size();
//        while (num--)
//        {
//            PII p = q.front();
//            q.pop();
//            int x = p.first;
//            int y = p.second;
//            if (x == n && y == m)
//                return sum;
//            for (int i = 0; i < 8; i++)
//            {
//                int xx = x + brr[i].first;
//                int yy = y + brr[i].second;
//                if (xx == 0 || yy == 0 || xx > n || yy > m || arr[xx][yy] == 1 || is[xx][yy])continue;
//                q.push({ xx,yy });
//                is[xx][yy] = 1;
//            }
//        }
//        sum++;
//
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];
//    cout << bfs();
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef pair<int, int> PII;
//const int N = 2e5;
//int h[N], e[N], ne[N], bian[N];
//int idx;
//int n, m;
//void add(int a, int b, int c)
//{
//    bian[idx] = c, e[idx] = b; ne[idx] = h[a], h[a] = idx++;
//}
//priority_queue<PII,vector<PII>,greater<PII>>pq;
//bool is[N];
//int dis[N];
//void dijie()
//{
//    memset(dis, 0x3f, sizeof dis);
//    dis[1] = 0;
//    pq.push({ dis[1],1 });
//    for (int i = 1; i <= n; i++)
//    {
//        PII n = pq.top();
//        int x = n.first;
//        int y = n.second;
//        if (is[y])continue;
//        is[y] = 1;
//        for (int j = h[y]; ~j; j = ne[j])
//        {
//            dis[e[j]] = min(dis[e[j]], dis[y] + bian[j]);
//            if (is[e[j]] == 0)
//            {
//                pq.push({ dis[e[j]],e[j] });
//            }
//        }
//    }
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    cin >> n >> m;
//    while (m--)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//    }
//    dijie();
//    if (dis[n] == 0x3f3f3f3f)
//        cout << -1;
//    else
//        cout << dis[n];
//}
//#include<bits/stdc++.h>
//using namespace std;
//int n, m, k;
//struct date
//{
//    int a, b, c;
//};
//date arr[10010];
//int dis1[10010];
//int dis2[10010];
//void bellman()
//{
//    dis1[1] = 0;
//    for (int i = 1; i <= k; i++)
//    {
//        memcpy(dis2, dis1, sizeof dis1);
//        for (int i = 1; i <= m; i++)
//        {
//            int x = arr[i].a;
//            int y = arr[i].b;
//            int z = arr[i].c;
//            dis2[y] = min(dis1[y], dis1[x] + z);
//        }
//        memcpy(dis1, dis2, sizeof dis1);
//    }
//}
//int main()
//{
//    memset(dis1, 0x3f, sizeof dis1);
//    cin >> n >> m >> k;
//    for (int i = 1; i <= m; i++)
//        cin >> arr[i].a >> arr[i].b >> arr[i].c;
//    bellman();
//    if (dis1[n] == 0x3f3f3f3f)
//        cout << -1;
//    else
//        cout << dis1[n];
//}
//#include<bits/stdc++.h>
//using namespace std;
//queue<int>q;
//int dis[10010];
//int e[10010], ne[10010], h[10010], w[10010];
//int idx;
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//bool is[10010];
//int n, m;
//void spfa()
//{
//    
//    q.push(1);
//    dis[1] = 0;
//    is[1] = 1;//����Ҫ�ڶ��д��ظ��ĵ�
//    while (q.size())
//    {
//        int j = q.front();
//        q.pop();
//        is[j] = 0;
//        for (int k = h[j]; k != -1; k = ne[k])
//        {
//            if (dis[e[k]] > dis[j] + w[k])
//            {
//                dis[e[k]] = dis[j] + w[k];
//                if (0 == is[e[k]])
//                {
//                    is[e[k]] = 1;
//                    q.push(e[k]);
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//    }
//    memset(dis, 0x3f, sizeof h);
//    spfa();
//    if (dis[n] > 0x7f7f7f7f / 2)
//        cout << "impossible";
//    else
//        cout << dis[n];
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int dis[N];
//int e[N], ne[N], h[N], w[N];
//int idx;
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//bool is[N];
//int lujing[N];
//int n, m;
//queue<int>q;
//bool spfa()
//{
//    memset(dis, 0x3f, sizeof dis);
//
//    q.push(1);
//    dis[1] = 0;
//    is[1] = 1;//����Ҫ�ڶ��д��ظ��ĵ�
//    while (q.size())
//    {
//        int pos = q.front();
//        q.pop();
//        is[pos] = 0;
//        for (int i = h[pos]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dis[j] > dis[pos] + w[i])
//            {
//                dis[j] = dis[pos] + w[i];
//                lujing[j] = lujing[pos] + 1;
//                if (lujing[j] >= n)
//                    return 1;
//                if (0 == is[j])
//                {
//                    is[j] = 1;
//                    q.push(j);
//                }
//            }
//        }
//    }
//    return 0;
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    cin >> n >> m;
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//    }
//
//    if (spfa())
//        cout << "Yes";
//    else
//        cout << "No";
//
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int dis[N];
//int e[N], ne[N], h[N], w[N];
//int idx;
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//bool is[N];
//int lujing[N];
//int n, m;
//queue<int>q;
//bool spfa()
//{
//    //    memset(dis, 0x3f, sizeof dis);
//    dis[0] = 0;
//    is[0] = 1;//����Ҫ�ڶ��д��ظ��ĵ�
//    q.push(0);
//    while (q.size())
//    {
//        int pos = q.front();
//        q.pop();
//        is[pos] = 0;
//        for (int i = h[pos]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dis[j] > dis[pos] + w[i])
//            {
//                dis[j] = dis[pos] + w[i];
//                lujing[j] = lujing[pos] + 1;
//                if (lujing[j] >= n)
//                    return 1;
//                if (0 == is[j])
//                {
//                    is[j] = 1;
//                    q.push(j);
//                }
//            }
//        }
//    }
//    return 0;
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    cin >> n >> m;
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//    }
//    for (int i = 1; i <= n; i++)
//        add(0, i, -1);
//    if (spfa())
//        cout << "Yes";
//    else
//        cout << "No";
//
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[210][210];
//int n, m, k;
//void floyd()
//{
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= n; j++)
//            for (int k = 1; k <= n; k++)
//                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
//}
//int main()
//{
//    cin >> n >> m >> k;
//    memset(arr, 0x3f, sizeof arr);
//    for (int i = 1; i <= n; i++)arr[i][i] = 0;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        arr[x][y] = z;
//    }
//    floyd();
//    while (k--)
//    {
//        int x, y;
//        cin >> x >> y;
//        if (arr[x][y] > 0x3f3f3f3f / 2)
//            cout << "impossible" << endl;
//        else
//            cout << arr[x][y] << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int e[N], ne[N], h[N], w[N];
//int idx;
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//int n, m;
//int dis[N];
//bool is[N];
//int Prim()
//{
//    memset(dis, 0x3f, sizeof dis);
//    dis[1] = 0;
//    int sum = 0;
//    for (int i = 0; i < n; i++)
//    {
//        int t = -1;
//        for (int j = 1; j <= n; j++)
//        {
//            if (!is[j] && (t == -1 || dis[j] < dis[t]))
//                t = j;
//        }
//        is[t] = true;
//        sum += dis[t];
//        for (int j = h[t]; j != -1; j = ne[j])
//        {
//            int k = e[j];
//            if (dis[k] > w[j])
//            {
//                dis[k] = w[j];
//
//            }
//        }
//    }
//    return sum;
//}
//int main()
//{
//    cin >> n >> m;
//    memset(h, -1, sizeof h);
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//    }
//    cout << Prim();
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int e[N], ne[N], h[N], col[N];
//int idx;
//bool is[N];
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//bool dfs(int pos)
//{
//    if (is[pos])return 1;
//    is[pos] = 1;
//    for (int i = h[pos]; i != -1; i=ne[i])
//    {
//        int j = e[i];
//        int fcol = col[pos];
//        int scol = col[j];
//        if (scol == 0)
//        {
//            col[j] = 3 ^ fcol;
//            int x = dfs(j);
//            if (x == 0)return 0;
//        }
//        else if ((scol^fcol)==3);
//        else return 0;
//    }
//    return 1;
//}
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    memset(h, -1, sizeof h);
//    for (int i = 0; i < m; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add(a, b);
//        add(b, a);
//    }
//    col[1] = 1;
//    if (dfs(1))
//    {
//        cout << "Yes";
//    }
//    else
//        cout << "No";
//}
//#include<bits/stdc++.h>
//using namespace std;
//bool st[1010];
//int n1, n2, m;
//const int N = 1e5 + 10;
//int e[N], ne[N], h[N];
//int idx;
//int match[1010];
//bool find(int x)//x�Ƿ�����ҵ�����
//{
//    for (int i = h[x]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (st[j])continue;
//        st[j] = 1;
//        if (match[j] == 0 || find(match[j]))
//        {
//            match[j] = x;
//            return 1;
//        }
//    }
//    return 0;
//}
//int xvliya()
//{
//    int sum = 0;
//    for (int i = 1; i <= n1; i++)
//    {
//        memset(st, 0, sizeof st);
//        if (find(i))
//            sum++;
//    }
//    return sum;
//}
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    cin >> n1 >> n2 >> m;
//    while (m--)
//    {
//        int a, b;
//        cin >> a >> b;
//        add(a, b);
//    }
//    cout << xvliya();
//}
//#include<bits/stdc++.h>
//using namespace std;
//int N, V;
//int dp[1010];
//int main()
//{
//    for (int i = 1; i <= N; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        for (int j = V; j >= a; j--)
//        {
//            dp[j] = max(dp[j], dp[j - a] + b);
//        }
//    }
//    cout << dp[V];
//}
//#include<bits/stdc++.h>
//using namespace std;
//int dp[2010];
//int main()
//{
//    int N, V;
//    cin >> N >> V;
//    for (int i = 1; i <= N; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        for (int k = 1; k <= c; k *= 2)
//        {
//            a *= 2, b *= 2;
//            for (int j = V; j >= b; j--)
//            {
//                dp[j] = max(dp[j - a] + b, dp[j]);
//            }
//        }
//
//    }
//    cout << dp[V];
//}
//#include<bits/stdc++.h>
//using namespace std;
//int dp[1010][1010];
//int main()
//{
//    int n1, n2;
//    string s1, s2;
//     memset(dp,0x3f3f3f3f,sizeof dp);
//
//    cin >> n1 >> s1 >> n2 >> s2;
//    s1 = " " + s1;
//    s2 = " " + s2;
//    for (int i = 0; i <= n1; i++)dp[i][0] = i;
//    for (int i = 0; i <= n2; i++)dp[0][i] = i;
//    for (int i = 1; i <= n1; i++)
//        for (int j = 1; j <= n2; j++)
//        {
//            if (s1[i] == s2[j])
//                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
//            else
//            {
//                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
//                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
//                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
//            }
//        }
//    cout << dp[n1][n2];
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[11][11];
//vector<string>v;
//int dis(string s1, string s2)
//{
//
//    s1 = " " + s1, s2 = " " + s2;
//    for (int i = 1; i < s1.size(); i++)
//        for (int j = 1; j < s2.size(); j++)
//        {
//            if (s1[i] == s2[j])
//                arr[i][j] = arr[i - 1][j - 1];
//            else arr[i][j] = min({ arr[i - 1][j - 1],arr[i - 1][j],arr[i][j - 1] }) + 1;
//        }
//    return arr[s1.size() - 1][s2.size() - 1];
//}
//int main()
//{
//    for (int i = 0; i <= 10; i++)arr[i][0] = i;
//    for (int i = 0; i <= 10; i++)arr[0][i] = i;
//    int n, m;
//    cin >> n >> m;
//    while (n--)
//    {
//        string s;
//        cin >> s;
//        v.push_back(s);
//    }
//    while (m--)
//    {
//        int sum = 0;
//        string s;
//        cin >> s;
//        int len = 0;
//        cin >> len;
//        for (int i = 0; i < v.size(); i++)
//        {
//            int n = dis(v[i], s);
//            if (n <= len)
//                sum++;
//        }
//        cout << sum << endl;;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//int count(int n, int x)//1~n�з����ֵ�����x�Ĵ���
//{
//    if (!n)return 0;//����nΪ0
//    vector<int>num;
//    while (n)
//    {
//        num.push_back(n % 10);
//        n /= 10;
//    }
//    int sum = 0;
//    for (int i = num.size() - 1; i >= 0; i--)
//    {
//        int a = 0, b = 0;
//        if (i == num.size() - 1 && !x)continue;
//        int NUM = 0;
//        for (int j = num.size() - 1; j > i; j--)
//            NUM = NUM * 10 + num[j];
//        if (x == 0)
//            NUM--;
//        NUM *= pow(10, i);
//        if (num[i] < x)
//        {
//            sum += NUM;
//            continue;
//        }
//        if (num[i] > x)
//            NUM += pow(10,i);
//        else
//        {
//            int NUM1 = 0;
//            for (int j = i - 1; j >= 0; j--)
//                NUM1 = NUM1 * 10 + num[j];
//            NUM++;
//            NUM += NUM1;
//        }
//        sum += NUM;
//    }
//    return sum;
//}
//int main()
//{
//    int a = 1, b = 1;
//    cin >> a >> b;
//    while (a || b)
//    {
//        if (a < b)
//           swap(a, b);
//        for (int i = 0; i < 10; i++)
//        {
//            int num1 = count(a-1, i);
//            int num2 = count(b, i);
//            cout << num2 - num1 << ' ';
//        }
//        cout << endl;
//        cin >> a >> b;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[22][22];
//int dp[1024 * 1024 + 10][22];
//int main()
//{
//    int n;
//    cin >> n;
//    memset(dp, 0x3f, sizeof dp);
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)cin >> arr[i][j], arr[j][i] = arr[i][j];
//    for (int i = 0; i < n; i++)
//        dp[1 << i][i] = 0;
//    for (int i = 0; i < 1 << n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            for (int k = 0; k < n; k++)
//            {
//                if ((i << k) & 1)
//                    dp[i][j] = min(dp[i][j], dp[i ^ (1 << k)][k] + arr[k][j]);
//            }
//        }
//    }
//    int Min = 0x3f3f3f3f3;
//    int len = 1 << n;
//    for (int i = 0; i < n; i++)
//        Min = min(Min, dp[len][i]);
//    cout << Min;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int e[6010], ne[6010], h[6010];
//int idx;
//int n;
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//int w[6010];
//int dp[6010][2];
//int Max;
//bool is[6010];
//void func(int f)
//{
//    dp[f][1] += w[f];
//    for (int i = h[f]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        func(j);
//        dp[f][0] += max(dp[j][0], dp[j][1]);
//        dp[f][1] += dp[j][0];
//    }
//}
//int main()
//{
//    cin >> n;
//    memset(h, -1, sizeof h);
//    for (int i = 1; i <= n; i++)
//        cin >> w[i];
//    for (int i = 0; i < n - 1; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add(b, a);
//        is[a] = 1;
//    }
//    for (int i = 1; i <= n; i++)
//        if (is[i] == 0)
//            func(i);
//    cout << max(dp[1][0], dp[1][1]);
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[310][310];
//int n, m;
//int Max;
//pair<int, int>brr[4] = { {0,1},{0,-1},{1,0},{-1,0} };
//int num[310][310];
//int dfs(int x, int y)
//{
//    if (num[x][y] != -1)
//        return num[x][y];
//    int sum = 0;
//    for (int i = 0; i < 4; i++)
//    {
//        int xx = x + brr[i].first;
//        int yy = y + brr[i].second;
//        if (!xx || !yy || xx > n || yy > m || arr[x][y] <= arr[xx][yy])continue;
//            sum = max(dfs(xx, yy), sum);
//        // cout<<sum<<" ";
//    }
//    sum++;
//    return num[x][y]=sum;
//}
//int main()
//{
//    memset(num, -1, sizeof num);
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            Max = max(Max, dfs(i, j));
//    cout << Max;
//
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef pair<int, int>PII;
//PII arr[100010];
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 0; i < n; i++)cin >> arr[i].first >> arr[i].second;
//    sort(arr, arr + n);
//    int r = 0;
//    int sum = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (i == 0)
//        {
//            r = arr[i].second;
//            sum++;
//        }
//        else
//        {
//            if (arr[i].first < r)r = min(r, arr[i].second);
//            else
//            {
//                r = arr[i].second;
//                sum++;
//            }
//        }
//    }
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//pair<int, int>arr[100010];
//bool les(pair<int, int>a, pair<int, int>b)
//{
//    return a.second < b.second;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 0; i < n; i++)cin >> arr[i].first >> arr[i].second;
//    sort(arr, arr + n, les);
//    int sum = 0;
//    int r = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (i == 0)
//        {
//            sum++;
//            r = arr[i].second;
//        }
//        else
//        {
//            if (arr[i].first <= r);
//            else
//            {       r = arr[i].second;
//            sum++;
//        }
//        }
//    }
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef pair<int, int> PII;
//PII arr[100010];
//int main()
//{
//    int l, r;
//    cin >> l >> r;
//    int n;
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i].first >> arr[i].second;
//    }
//    sort(arr, arr + n);
//    int sum = 0;
//    int Max_r = -2e9;
//    for (int i = 0; i < n; i++)
//    {
//        
//        for (int j = i; j < n; j++)
//            if (arr[j].first <= l)
//                Max_r = max(Max_r, arr[j].second);
//        if (Max_r < l)
//        {
//            sum = -1;
//            break;
//        }
//        else
//        {
//            sum++;
//            if (Max_r >= r)
//                break;
//            l = Max_r;
//        }
//    }
//    if (Max_r < r)
//        cout << -1;
//    else
//        cout << sum;
//}
//#include <bits/stdc++.h>
//using namespace std;
//struct date {
//    long long a, b;
//    bool operator<(date d1)const
//    {
//        return a < d1.a;
//    }
//}date[100010];
//long long sum[50010];
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 1; i <= n; i++)cin >> date[i].a >> date[i].b;
//    sort(date + 1, date + n + 1);
//    for (int i = 1; i <= n; i++)
//        sum[i] = sum[i - 1] + date[i].a;
//    long long ans = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        ans += max<long long>(0, sum[i - 1] - date[i].b);
//    }
//    cout << ans;
//}
//#include<bits/stdc++.h>
//using namespace std;
//bool is[10000000];
//vector<int>v;
//int n;
//void line()
//{
//    for (int i = 2; i <= n; i++)
//    {
//        if (!is[i])v.push_back(i);
//        for (int j = 0; v[j] * i <= n; j++)
//        {
//            is[i * v[j]] = 1;
//            if (i % v[j] == 0)break;
//        }
//    }
//}
//int main()
//{
//
//    cin >> n;
//    line();
//    cout << v.size();
//}
//#include<bits/stdc++.h>
//#include<set>
//using namespace std;
//set<int>s;
//void func(int x)
//{
//    s.clear();
//    for (int i = 1; i * i <= x; i++)
//    {
//        if (x % i == 0)
//        {
//            if (i * i == x)
//                s.insert(x);
//            else
//                s.insert(i), s.insert(x / i);
//        }
//    }
//    for (auto i : s)
//        cout << i << ' ';
//    cout << endl;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        int x;
//        cin >> x;
//        func(x);
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//map<int, int>mp;
//const int N = 1e9 + 7;
//void func(int x)
//{
//    if (x == 1)
//        return;
//    for (int i = 2; i * i <= x; i++)
//        if (x % i == 0)
//        {
//            int cnt = 0;
//            while (x % i == 0)
//            {
//                cnt++;
//                x /= i;
//            }
//            mp[i] += cnt;
//        }
//
//}
//int main()
//{
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        int x;
//        cin >> x;
//        func(x);
//    }
//    long long sum = 1;
//    for (auto i : mp)
//    {
//        sum = sum * (i.second + 1);
//        sum %= N;
//    }
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e9 + 7;
//int sum = 1;
//int f(int x, int y)
//{
//    int ans = 1;
//    int X = x;
//    while (y--)
//    {
//        ans += x;
//        x *= X;
//        ans %= N;
//        x %= N;
//    }
//    return ans;
//}
//map<int, int>mp;
//void func(int x)
//{
//
//    for (int i = 2; i * i <= x; i++)
//    {
//        if (x % i == 0)
//        {
//            int cnt = 0;
//            while (x % i == 0)
//            {
//                x /= i;
//                cnt++;
//            }
//            mp[i] = cnt;
//        }
//    }
//    if (x > 1)
//        mp[x]++;
//
//
//}
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int x;
//
//        cin >> x;
//        func(x);
//    }
//    if (mp.size() == 0);
//    else
//    {
//        for (auto i : mp)
//        {
//            sum *= f(i.first, i.second);
//            sum %= N;
//        }
//    }
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef unsigned long long ULL;
//const int N = 1e9 + 7;
//unordered_map<int, int>mp;
//int main()
//{
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        int x;
//        cin >> x;
//        for (int i = 2; i <= x / i; i++)
//        {
//            while (x % i == 0)
//            {
//                x /= i;
//                mp[i]++;
//            }
//
//        }
//        if (x > 1)
//            mp[x]++;
//    }
//    ULL sum = 1;
//    for (auto a : mp)
//    {
//        ULL k = 0;
//        for (int j = 0; j <= a.second; j++)
//        {
//            k = (k * a.first + 1) % N;
//        }
//        sum *= k;
//        sum %= N;
//
//    }
//    cout << sum % N;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//bool is[1000010];
//int num[1000010]��
//vector<int>v;
////1��ŷ��������1
//void func(int n)
//{
//    for (int i = 2; i <= n; i++)
//    {
//        if (!is[i])
//        {
//            v.push_back(i);
//            num[i] = i - 1;
//        }
//        for (int j = 0; v[j] * i <= n; j++)
//        {
//            is[v[j] * i] = 1;
//            num[v[j] * i] = num[i] * (v[j] - 1) / v[j];
//            if (i % v[j] == 0)break;
//        }
//    }
//    long long sum = 0;
//    for (int i = 1; i <= n; i++)
//        sum += num[i];
//    return sum;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    cout << func(n);
//}
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const LL N = 1e9 + 7;

// LL qmi(LL a, LL b, LL c)
// {
//     LL sum = 1;
//     while (b)
//     {
//         if (b % 2)
//             sum = sum * a % c;
//         a = a * a % c;
//         b >>= 1;
//     }
//     return sum;
// }
// LL arr[100010];
// LL brr[100010];
// void init()
// {
//     arr[0] = 1;
//     for (int i = 1; i <= 100000; i++)
//         arr[i] = arr[i - 1] * i % N;
//     for (int i = 0; i <= 100000; i++)
//     {
//         brr[i] = qmi(arr[i], N - 2, N);
//     }
// }
// int main()
// {
//     init();
//     int n;
//     cin >> n;
//     while (n--)
//     {
//         int a, b;
//         cin >> a >> b;
//         cout << arr[a] * brr[b]%N * brr[a - b]%N << endl;
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const int N = 1e5+10;
// int arr[N];
// int gcd(int a,int b){
//     return b?gcd(b,a%b):a;
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         int num[5010]={0};
//         int n;
//         cin>>n;set<int>S1;
//         for(int i=1;i<=n;i++){
//             cin>>arr[i];
//             num[arr[i]]++;
//             S1.insert(arr[i]);
//             }
        
//         int g=arr[1];
//         for(int i=1;i<=n;i++)g=gcd(g,arr[i]);
//         int ans=n-max(1,num[g]);
//         int k=0;
//         while((*S1.begin())!=g){
//             k++;
           
//             set<int>S2;
//             for(int i=1;i<=n;i++)
//             {
//                 for(auto x:S1){
//                     int y=gcd(x,arr[i]);
//                     S2.insert(y);
//                     if(y==2)cout<<x<<' '<<arr[i]<<endl;
//                 }
//                  for(auto x:S2)cout<<x<<' ';
//             cout<<endl;
//                 S1=S2;
//             }
//             //std::cout<<(*S1.begin())<<endl;
//         }
//         cout<<ans<<k<<endl;
//     }
// }
// #include<iostream>
// #include<algorithm>
// using namespace std;
// int arr[1010][1010];
// int dp[1010][1010][2];
// int main(){
//     memset(dp,-0x3f,sizeof dp);
//     int n,m;
//     cin>>n>>m;
//     for(int i=1;i<=n;i++)
//         for(int j=1;j<=m;j++)cin>>arr[i][j];
//     //0是从上到下，1是从下到上，我们规定从左到右也属于0
//     dp[1][1][1]=dp[1][1][0]=arr[1][1];
// for(int j=1;j<=m;j++){
//     for(int i=1;i<=n;i++)
//         dp[i][j][0]=max({dp[i][j-1][0],dp[i][j-1][1],dp[i-1][j][0]})+arr[i][j];
//      for(int i=n;i;i--)
//         dp[i][j][1]=max({dp[i][j-1][0],dp[i][j-1][1],dp[i+1][j][1]})+arr[i][j];
//         for(int i=1;i<=n;i++)
//         cout<<i<<' '<<j<<' '<<dp[i][j][0]<<' '<<dp[i][j][1]<<endl;
// }
//     cout<<dp[n][m][0];
//     return 0;
// }